package com.leetcode.No0029;

import org.junit.Test;

/**
 * @program: leetcode
 * @description: 两数相除
 * @author: wangzhihua
 * @date: 2021-07-18
 */
public class Solution01 {

	@Test
	public void test01() {
//		System.out.println(divide(10, 3));
//		System.out.println(divide(7, -3));
//		System.out.println(divide(0x7fffffff, -1));
		System.out.println(divide(-2147483648, -1));
	}

	public int divide(int dividend, int divisor) {
		boolean diffSign = (dividend ^ divisor) < 0;

		long remainder = Math.abs((long) dividend);
		long originalDivisor = Math.abs((long) divisor);
		long longDivisor;

		long ans = 0;

		while (remainder >= originalDivisor) {
			int step = 0;
			do {
				longDivisor = originalDivisor << step;
			} while (remainder >= longDivisor && ++step > 0);
			if ((longDivisor >> 1) >= originalDivisor) {
				remainder -= (longDivisor >> 1);
				ans += ((long) 1) << --step;
			}
		}

		if (!diffSign && ans > Integer.MAX_VALUE)
			return Integer.MAX_VALUE;
		return diffSign ? -(int) ans : (int) ans;
	}

}
